package com.ycy.leetcode.tree;

import com.google.common.collect.Lists;
import org.junit.Before;
import org.junit.Test;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BSTCengXu1 {

  static class TreeNode {
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val) {
      this.val = val;
    }
  }

  TreeNode treeNode = null;

  @Before
  public void before() {


    /*
      500
       / \
    200  1000
    / \      / \
   100 400 700  1500
     */

    TreeNode treeNode = new TreeNode(500);
    treeNode.left = new TreeNode(200);
    treeNode.left.left = new TreeNode(100);
    treeNode.left.right = new TreeNode(400);

    treeNode.right = new TreeNode(1000);
    treeNode.right.left = new TreeNode(700);
    treeNode.right.right = new TreeNode(1500);

    this.treeNode = treeNode;
  }

  @Test
  public void test() {
    List<List<Integer>> cengxubianli = cengxubianli(this.treeNode);
    System.out.println(cengxubianli);
  }

  /**
   * 宽度优先搜索 层序遍历
   * 使用什么数据结构存放节点 怎么保存数据
   * 1.使用队列
   * 2.两层循环
   */
  public List<List<Integer>> cengxubianli(TreeNode treeNode) {
    List<List<Integer>> list = Lists.newArrayList();

    Queue<TreeNode> linkedList = new LinkedList<>();
    linkedList.offer(treeNode);

    while (!linkedList.isEmpty()) {
      int size = linkedList.size();
      List<Integer> level = Lists.newLinkedList();
      for (int i = 0; i < size; i++) {
        TreeNode poll = linkedList.poll();
        level.add(poll.val);
        if (poll.left != null) linkedList.offer(poll.left);
        if (poll.right != null) linkedList.offer(poll.right);

      }
      list.add(level);

    }
    return list;
  }

  public List<List<Integer>> list = Lists.newArrayList();

  //深度优先搜索 前序遍历
  public void cengxubianli2(TreeNode treeNode, int i) {
    if (treeNode == null) return;

    if (list.size() < i) {
      list.add(Lists.newArrayList());

    }
    List<Integer> integers1 = list.get(i - 1);
    integers1.add(treeNode.val);

    int i1 = ++i;
    cengxubianli2(treeNode.left, i1);
    cengxubianli2(treeNode.right, i1);
  }

  @Test
  public void test2() {
    cengxubianli2(this.treeNode, 1);
    System.out.println(this.list);
  }

}
